本章介绍并实现更基本、更常用的两种数据结构——栈和队列。与之前介绍的向量和列表一样，同属于线性序列结构，故其中存放的数据对象之间也具有线性次序。相对于一般的序列结构，栈与队列的数据操作范围仅限于逻辑上的特定某端。

4.1 栈

4.1.1 ADT接口

入栈与出栈

栈（Stack） 是存放数据对象的一种特殊容器，其中的数据元素按线性的逻辑次序排列，故也可定义首、末元素。栈结构的插入和删除操作仅限于栈的某一特定端，即若约定新的元素只能从某一端插入其中，则反过来只能从这一端删除已有的元素。禁止操作的另一端称作盲端。

栈中可操作的一端被称作为栈顶（stack top） ，而另一无法直接操作的盲端被称为栈底（stack bottom）。插入和删除操作分别被称作入栈（push） 和出栈（pop）。

操作接口	功能
`size()`	报告栈的规模
`empty()`	判断栈是否为空
`push(e)`	将e插至栈顶
`pop()`	删除栈顶对象
`top()`	引用栈顶对象

后进先出

栈中元素接收操作的次序必然始终遵循所谓的“后进先出（last-in-first-out，LIFO）”的规律：从栈结构的整个生命期来看，更晚（早）出栈的元素，应为更早（晚）入栈者；反之，更晚（早）入栈者应更早（晚）出栈。

4.1.3 Stack模板类

由于栈可视作序列的特例，因此可将栈作为向量的派生类。利用C++的继承机制，基于之前定义的向量模板类实现栈结构并将接口重新命名。

// stack@vector.h
// 代码4.1 Stack模板类

#include "../Vector/Vector.h"
template <typename T> class Stack: public Vector<T> { // 将向量的首/末端作为栈底/顶
public: // size()、empty()以及其它开放接口，均可直接沿用
    void push (T const& e) { insert(size(), e); } // 入栈：等效于将新元素作为向量的末元素插入
    T pop() { return remove(size() - 1); } // 出栈：等效于删除向量的末元素
    T& top() { return (*this)[size() - 1]; } // 取顶：直接返回向量的末元素
};

由于栈操作都限制于向量的末端，参与操作的元素没有任何后继，因此栈接口的时间复杂度均为常数。

同理，也可基于List模板类派生出Stack类。（习题【4-1】）

特别说明一下：top()操作的位置不可颠倒，因为如果插入和删除操作都集中在前端进行，那么每一次操作都要涉及到向量中的当前所有元素，于是入栈和出栈操作的复杂度都上升到$O(n)$。

4.2 栈与递归

习题【1-17】指出，递归算法所需的空间量，主要决定于最大递归深度。在达到这一时刻，同时活跃的递归实例达到最多。

通过栈可以解决如下问题：

操作系统具体是如何实现函数（递归）调用的？
如何记录调用与被调用函数（递归）实例之间的关系？
如何实现函数（递归）调用的返回？
如何维护同时活跃的所有函数（递归）实例的？

4.2.1 函数调用栈

在 Windows 等大部分操作系统中，每个运行中的二进制程序都配有一个调用栈（call stack）或执行栈（execution stack）。借助调用栈可以跟踪属于同一程序的所有函数，记录它们之间的相互调用关系，并保证在每一调用实例执行完毕之后，可以准确返回。

函数调用

调用栈的基本单位是帧（frame）。每次函数调用时，都会相应地创建一帧，记录该函数实例在二进制程序中的返回地址（return address），以及局部变量、传入参数等，并将该帧压入调用栈。若在该函数返回之前又发生新的调用，则同样地要将新函数对应的一帧压入栈中，成为新的栈顶。函数一旦运行完毕，对应的帧随即弹出，运行控制权将被交还给该函数的上层调用函数，并按照该帧中记录的返回地址确定在二进制程序中继续执行的位置。

在任一时刻，调用栈中的各帧，依次对应于那些尚未返回的调用实例，亦即当时的活跃函数实例（active function instance）。特别地，位于栈底的那一帧必然对应于入口主函数main()，若它从调用栈中弹出，则意味着整个程序的运行结束，此后控制权将交还给操作系统。

仿照递归跟踪法，程序执行过程出现过的函数实例及其调用关系，也可构成一棵树，，称作该程序的运行树。任一时刻的所有活跃函数实例，在调用栈中自底到顶，对应于运行树中从根节点到最新活跃函数实例的一条调用路径。

此外，调用栈中各帧还需存放其他内容。比如，因各帧规模不一，它们还需记录前一帧的起始地址，以保证其出栈之后前一帧能正确地恢复。

递归

作为函数调用的特殊形式，递归也可借助上述调用栈得以实现。同一函数可能同时拥有多个实例，并在调用栈中各自占有一帧。这些帧的结构完全相同，但其中同名的参数或变量，都是独立的副本。

4.2.2 避免递归

系统在后台隐式地维护调用栈的过程中，难以区分哪些参数和变量是对计算过程有实质作用的，更无法以通用的方式对它们进行优化，因此不得不将描述调用现场的所有参数和变量悉数入栈。更加上每一帧都必须保存的执行返回地址以及前一帧起始位置，往往会导致程序的空间效率不高甚至极低；同时，隐式的入栈和出栈操作也会令实际的运行时间增加不少。

因此在追求高效率的场合，应尽可能地避免递归。可以考虑使用将尾递归转换为等效的迭代形式（1.4.4节介绍过）或者采用动态规划策略将 Fibonacci数算法中的二分递归改为线性递归，直至完全消除递归（1.4.5节）。

这样做的话，尽管算法原递归版本的高度概括性和简洁性将大打折扣，但毕竟在空间效率方面可以获得足够的补偿。

4.3 栈的典型应用

4.3.1 逆序输出

逆序输出类问题特征：首先，虽有明确的算法，但其解答却以线性序列的形式给出；其次，无论是递归还是迭代实现，该序列都是依逆序计算输出的；最后，输入和输出规模不确定，难以事先确定盛放输出数据的容器大小。因其特有的“后进先出”特性及其在容量方面的自适应性，使用栈来解决此类问题可谓恰到好处。

进制转换

给定任一10进制非负整数，将其转换为其他进制表示形式。若使用向量，则扩容策略必须得当；若使用列表，则多数接口均被闲置；使用栈栈，即可满足以上要求，又可有效控制计算成本。

递归实现

// convert_a.cpp
// 代码4.2 进制转换算法（递归版）

void convert(Stack<char>& S, __int64_t n, int base){ // 十进制正整数n到base进制的转换(递归版)
    static char digit[] // 0 < n, 1 < base <= 16, 新进制下的数位符号，可视base取指范围适当扩充
            = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
    if (0 < n) { // 在尚有余数之前，反复地
        S.push(digit[n % base]); // 逆向记录当前最低位，再
        convert(S, n/base, base); // 通过递归得到所有更高位
    }
} // 新进制下由高到低的各数位，自顶向下保存于栈S中

main(){
    Stack<char> S; convert(S, n, base); // 用栈记录转换得到的各数位
    while(!S.empty()) printf("%c", S.pop()); // 逆序输出
}

尽管新进制下的各数位须由低到高次序算出，但只要引入一个栈并将算得的数位依次入栈，则在计算结束后只需通过反复的出栈操作即可由高到低将其顺序输出。

这里的静态数位符号表在全局只需保留一份，但与一般的递归函数一样，该函数在递归调用栈中的每一帧都仍需记录参数S、n和base。将它们改为全局变量固然可以节省这部分空间，但依然不能彻底地避免因调用栈操作而导致的空间和时间消耗。为此，可将其改写为迭代形式，既能充分发挥栈处理此类问题的特长，又可将空间消耗降至$O(1)$。

迭代实现

// convert_b.cpp
// 代码4.3 进制转换算法（迭代版）

void convert(Stack<char>& S, __int64_t n, int base){ // 十进制数n到base进制的转换(迭代版)
    static char digit[] // 0 < n, 1 < base <= 16, 新进制下的数位符号，可视base取指范围适当扩充
            = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
    while (n > 0){ // 由低到高，逐一计算出新进制下的各数位
        int remainder = (int) (n % base); S.push(digit[remainder]); // 余数(当前位)入栈
        n /= base; // n更新为其对base的除商
    }
} // 新进制下由高到低的各数位，自顶向下保存于栈S中

main(){
    Stack<char> S; convert(S, n, base); // 用栈记录转换得到的各数位
    while(!S.empty()) printf("%c", S.pop()); // 逆序输出
}

4.3.2 递归嵌套

递归嵌套类问题特征：具有自相似性的问题多可嵌套地递归描述，但因分支位置和嵌套深度并不固定，其递归算法的复杂度不易控制。栈结构及其操作天然地具有递归嵌套性，故可用以高效地解决这类问题。

栈混洗

栈混洗问题定义：考察三个栈 A、B 和 S。其中，B 和 S 初始为空；A 含有 n 个元素，自顶向下构成输入序列：
$A = < a_1,a_2,…,a_n ]$
这里，分别用尖括号、方括号示意栈顶、栈底。
以下，若只允许通过S.push(A.pop())弹出栈 A 的顶元素并随即压入栈 S 中，或通过B.push(S.pop())弹出 S 的顶元素并随即压入栈 B 中，则在经过这两类操作各 n 次之后，栈 A 和 S 有可能均为空，原 A 中的元素均已转入栈 B 。此时，若将 B 中元素自底向上构成的序列记作：
$B = [ a_{k1},a_{k2},…,a_{kn} >$
则该序列称作原输入序列的一个栈混洗（stack permutation）。

除了“实施出栈操作时栈不得为空”，以上过程并无更多限制，故栈混洗并不唯一。

一般地对于长度为 n 的输入序列，每一栈混洗都对应于由栈 S 的 n 次push和 n 次 pop构成的某一合法操作序列。反之，由 n 次push和 n 次pop构成的任何操作序列，只要满足“任一前缀中push不少于pop”这一限制，则该序列也必然对应于一个栈混洗（习题【4-4】）

计数（PPT P340）

长度为 n 的序列可能栈混洗总数:
$$
\begin{aligned}
SP & = \sum_{k = 1}^n SP(k-1) \cdot SP(n-k) \
& = Catalan(n) \
& = \frac{(2n)!}{(n+1)!n!} \
\end{aligned}
$$
其中，$k$为第$k$次pop()操作。

甄别（PPT P342）

甄别是判断新生成的序列能否经过栈混洗原序列得到。

充要条件（1）：对于任何$1 \leq i < j < k \leq n$，$ […,k,…,i,…，j,…>$并非栈混洗。A permutation is a stack permutation iff it does NOT involve the permutation 312.——Knuth, 1968（习题【4-3】，由此可得到一个$O(n^3)$的甄别算法。

充要条件（2）：$[p_1,p_2,p_3,….,p_n>$是$<1,2,3,…,n]$的栈混洗，当且仅当对于任意$i < j$，不含模式$[…,j+1,…,i,…,j,…>$，由此可得到一个$O(n^2)$的甄别算法。

$O(n)$算法：直接借助栈A、B 和 S ，模拟混洗过程。每次S.pop()之前，检查 S 是否已空；或需弹出的元素在 S 中，却非顶元素。

括号匹配

括号匹配问题定义：对任一程序块，判断其中的括号是否在嵌套定义下完全匹配（简称匹配）。

递归实现

构思：先只考虑圆括号。用“+”表示表达式的串接。
一般地，若表达式S可分解为如下格式：
$S = S_0 + “(“ + S_1 + “)” + S_2 + S_3$
其中$S_0$和$S_3$不含括号，且$S_1$中左、右括号数目相等，则S匹配当且仅当$S_1$和$S_2$均匹配。
按照这一理解，可采用分治策略设计算法如下：将表达式划分为子表达式$S_0$、$S_1$和$S_2$，分别递归地判断$S_1$和$S_2$是否匹配。这一构思代码实现如下：

// nest_a.cpp
// 代码4.4 括号匹配算法（递归版）

void trim(const char exp[], int& lo, int& hi){ // 删除exp[lo, hi]不含括号的最长前缀、后缀
    while ((lo <= hi) && (exp[lo] != '(') && (exp[lo] != ')')) lo++; // 查找第一个和最后一个括号
    while ((lo <= hi) && (exp[hi] != '(') && (exp[hi] != ')')) hi--;
}

int divide(const char exp[], int lo, int hi){ // 切分exp[lo, hi], 使exp匹配仅当子表达式匹配
    int mi = lo; int crc = 1; // crc为[lo, mi]范围内左、右括号数目之差
    while ((0 < crc) && (++mi < hi)) // 逐个检查各字符，直到左、右括号数目相等，或者越界
    {if (exp[mi] == ')') crc--; if (exp[mi] == '(') crc++; } // 左、右括号分别计数
    return mi; // 若mi <= hi,则为合法切分点；否则，意味着局部不可能匹配
}

bool paren(const char exp[], int lo, int hi){ // 检查表达式exp[lo,hi]是否括号匹配(递归版)
    trim(exp, lo, hi); if (lo > hi) return true; // 清除不含括号的前缀、后缀
    if (exp[lo] != '(') return false; // 首字符非左括号，则必不匹配
    if (exp[hi] != ')') return false; // 末字符非右括号，则必不匹配
    int mi = divide(exp, lo, hi); // 确定适当的切分点
    if (mi > hi) return false; // 切分点不合法，意味着局部以至整体不匹配
    return paren(exp, lo + 1, mi - 1) && paren(exp, mi + 1, hi); // 分别检查左、右子表达式
}

其中，trim()函数用于截除表达式中不含括号的头部和尾部，即前缀$S_0$和后缀$S_3$。divide()函数对表达式做线性扫描，并动态地记录已经扫描的左、右括号数目之差。如此，当已扫过同样多的左、右括号时，即确定了一个合适的切分点 mi ，并得到一个子表达式$S_1 = exp(lo,mi)$和$S_2 = exp(mi, hi]$。以下，经递归地检查$S_1$和$S_2$，即可判断原表达式是否匹配。

在最坏情况下divide()需要线性时间，且递归深度为$O(n)$，故以上算法共需$O(n^2)$时间。此外，该方法也难以处理含有多种括号的表达式（习题【4-5】和【4-15】），故有必要进一步优化。

特别说明：实际上若仅考虑一种括号，只需一个计数器即可，但推广至多种括号并存的情况，则不可以使用多个计数器，因为有括号嵌套的情况存在。（PPT P334）

迭代实现

实际上，只要将push、pop操作分别与左、右括号相对应，则长度为 n 的栈混洗，必然与由 n 对括号组成的合法表达式彼此对应（习题【4-4】）（n 个元素的栈混洗等价于 n 对括号的匹配）。按照这一理解，借助栈结构，只需扫描一趟表达式，即可在线性时间内，判定其中的括号是否匹配。

代码实现:

// nest_b.cpp
// 代码4.5 括号匹配算法（迭代版）

bool paren(const char exp[], int lo, int hi){ // 表达式括号匹配检查，可兼顾三种括号
    Stack<char> S; // 使用栈记录已发现但尚未匹配的左括号
    for (int i = lo; i <= hi; i++) /* 逐一检查当前字符 */
        switch (exp[i]) { // 左括号直接进栈；右括号若与栈顶失配，则表达式必不匹配
            case '(':
            case '[':
            case '{': S.push(exp[i]);
                break;
            case ')': if ((S.empty()) || ('(' != S.pop())) return false;
                break;
            case ']': if ((S.empty()) || ('[' != S.pop())) return false;
                break;
            case '}': if ((S.empty()) || ('{' != S.pop())) return false;
                break;
            default:
                break; // 非括号字符一律忽略
        }
    return S.empty(); // 整个表达式扫描过后，栈中若仍残留(左)括号，则不匹配；否则(栈空)匹配
}

新算法的流程控制简单，而且便于推广至多类括号并存的场合。

算法描述：它自左向右逐个考察各字符，忽略所有非括号字符。凡遇到左括号，无论属于哪类均统一压入栈 S 中。若遇右括号，则弹出栈顶的左括号与之比对。若二者属于同类，则继续检查下一字符；否则，即可断定表达式不匹配。同时若栈 S 提前变空或者表达式扫描过后栈 S 非空，同样意味着不匹配。

4.3.3 延迟缓冲

延迟缓冲类问题特征：在一些应用问题中，输入可分解为多个单元并通过迭代依次扫描处理，但过程中的各步计算往往滞后于扫描的进度，需要待到必要的信息已完整到一定程度之后，才能作出判断并实施计算。在这类场合，栈结构则可以扮演数据缓冲区的角色。

表达式求值

在编译 C++ 程序的预处理阶段，源程序中的所有常量表达式都需首先计算并替换为对应的具体数值。而在解释型语言中，算术表达式的求值也需随着脚本执行过程中反复进行。

可见，不能简单地按照“先左后右”的次序执行表达式中的运算符。关于运算符执行次序的规则（即运算优先级），一部分决定于事先约定的惯例（比如乘除优先于加减），另一部分则决定于括号。也就是说，仅根据表达式的某一前缀，并不能完全确定各运算符能否执行以及执行的次序；只有在已获得足够多后续信息之后，才能确定其中哪些运算符可以执行。

优先级表

// priority.h
// 代码4.6 运算符优先级关系的定义

#define N_OPTR 9 // 运算符总数
typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; // 运算符集合
// 加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符

const char pri[N_OPTR][N_OPTR] = { // 运算符优先等级[栈顶][当前]
        /*              |-------------------- 当 前 运 算 符 --------------------| */
        /*              +      -      *      /      ^      !      (      )      \0 */
        /* --  + */    '>',   '>',   '<',   '<',   '<',   '<',   '<',   '>',   '>',
        /* |   - */    '>',   '>',   '<',   '<',   '<',   '<',   '<',   '>',   '>',
        /* 栈  * */    '>',   '>',   '>',   '>',   '<',   '<',   '<',   '>',   '>',
        /* 顶  / */    '>',   '>',   '>',   '>',   '<',   '<',   '<',   '>',   '>',
        /* 运  ^ */    '>',   '>',   '>',   '>',   '>',   '<',   '<',   '>',   '>',
        /* 算  ! */    '>',   '>',   '>',   '>',   '>',   '>',   ' ',   '>',   '>',
        /* 符  ( */    '<',   '<',   '<',   '<',   '<',   '<',   '<',   '=',   ' ',
        /* |   ) */    ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',   ' ',
        /* -- \0 */    '<',   '<',   '<',   '<',   '<',   '<',   '<',   ' ',   '='
};

在常规的四则运算之外，这里还引入了乘方和阶乘运算。其中阶乘属于一元运算，且优先级最高。为统一算法的处理流程，将左、右括号以及标识表达式尾部的字符’\0’，也视作运算符。

求值算法

基于运算符优先级如上的定义和判定规则，可实现表达式求值算法如下：

// rpn.cpp
// 代码4.7 表达式的求值及RPN的转换

float evaluate(char* S, char*& RPN){ // 对(已剔除空白格的)表达式S求值，并转换为逆波兰式RPN
    Stack<float> opnd; Stack<char> optr; // 运算数栈、运算符栈
    optr.push('\0'); // 尾哨兵'\0'也作为头哨兵首先入栈
    while (!optr.empty()){ // 在运算符栈非空之前，逐个处理表达式中各字符
        if (isdigit(*S)){ // 若当前字符为操作数，则
            readNumber(S, opnd); append(RPN, opnd.top()); // 读入操作数，并将其接至RPN末尾
        } else // 若当前字符为运算符，则
        switch (orderBetween(optr.top(), *S)){ // 视其与栈顶运算符之间优先级高低分别处理
            case '<': // 栈顶运算符优先级更低时
                optr.push(*S); S++; // 计算推迟，当前运算符进栈
                break;
            case '=': // 优先级相等（当前运算符为右括号或者尾部哨兵'\0'）时
                optr.pop(); S++; // 脱括号并接收下一个字符
            case '>': {// 栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈
                char op = optr.pop();
                append(RPN, op); // 栈顶运算符出栈并续接至RPN末尾
                if ('!' == op) { // 若属于一元运算符
                    float pOpnd = opnd.pop(); // 只需取出一个操作数，并
                    opnd.push(calcu(op, pOpnd)); // 实施一元计算，结果入栈
                } else { // 对于其它（二元）运算符
                    float pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop(); // 取出后、前操作数
                    opnd.push(calcu(pOpnd1, op, pOpnd2)); // 实施二元计算，结果入栈
                }
                break;
            }
            default : exit(-1); // 逢语法错误，不做处理直接退出
        } // switch
    }// while
    return opnd.pop(); // 弹出并返回最后的计算结果
}

算法描述：该算法自左向右扫描表达式，并对其中字符逐一做相应的处理。那些已经扫描过但（因信息不足）尚不能处理的操作数与运算符，将分别缓冲至栈opnd和栈optr。一旦判定已缓存的子表达式优先级足够高（这里优先级足够高的意思是当前读取算符优先级低于栈顶算符的优先级），便弹出相关的操作数和运算符，随即执行运算，并将结果压入栈opnd。

留意这里区分操作数和运算符的技巧。一旦当前字符由非数字转为数字，则意味着开始进入一个对应于操作数的子串范围。由于这里允许操作数含有多个数位，甚至可能是小数，故可调用readNumber()函数（习题【4-6】），根据当前字符及其后续的若干字符，利用另一个栈解析出当前的操作数。解析完毕，当前字符将再次聚焦于一个非数字字符。

不同优先级的处置

按照代码4.7，若当前字符为运算符，则在调用orderBetween()函数（习题【4-7】），将其与栈optr的栈顶操作符做一比较之后，即可视二者的优先级高低，分三种情况相应地处置。

（1）若当前运算符的优先级更高，则optr中的栈顶元素运算符尚不能执行。
注意，根据代码4.6定义的优先级表，无论栈顶元素如何，当前操作符为’(‘的所有情况也统一按此处理。也就是说，所有左括号及其后紧随的一个操作符都会相继地被直接压入optr栈中，而此前的运算符则一律押后执行——这与左括号应有的功能完全吻合。

（2）反之，一旦栈顶运算符的优先级更高，则可以立即弹出并执行对应的运算。
同理，无论栈顶元素如何，当前操作符为’)’的情况也几乎全部归入这一处理方式。也就是说，一旦抵达右括号，此前在optr栈缓冲的运算符大都可以逐一弹出并执行——这与右括号应有的功能也完全吻合。

（3）当前运算符与栈顶运算符的优先级“相等”。
对右括号的上述处理方式，将在optr栈顶出现操作符’(‘时终止——由代码4.6可知,pri['('][')'] = '>'。此时，将弹出栈顶的’(‘，然后继续处理’)’之后的字符。这对左、右括号在表达式中必然相互匹配，其作用在于约束介乎二者之间的那段子表达式的优先级关系，故在其“历史使命”完成之后，算法做如上处置理所应当。

除左、右括号外，还有一种优先级相等的合法情况，即pri['\0']['\0'] = '='。由于在算法启动之初已经首先将字符’\0’压入optr栈，故在整个表达式已被正确解析并抵达表达式结束标识符’\0’时，即出现这一情况。对于合法的表达式，这种情况只在算法中介前出现一次，算法将这种情况按照优先级相等的方式处置。

语法检查及鲁棒性

为简洁起见，以上算法假设输入表达式的语法完全正确；否则，有可能会导致荒诞的结果。习题【4-12】在此基础上尝试扩充语法语法以及对各种非法情况的处理功能。

4.3.4 逆波兰表达式

RPN

逆波兰表达式（reverse Polish notation，RPN）是数学表达式的一种，其语法规则可概括为：操作符紧邻于对应的（最后一个）操作数之后。

RPN表达式亦称作后缀表达式（postfix），原表达式则称作中缀表达式（infix）。尽管RPN表达式不够直观易读，但其对算符优先级的表述能力，却毫不逊色于常规的中缀表达式；而且其在计算效率方面的优势，更是常规表达式无法比拟的。RPN表达式中优先级的执行次序，可更为简洁地确定，既不必在实现做任何规定，更无需借助括号强制改变优先级。具体而言，各运算符被执行的次序，与其在RPN表达式中出现的次序完全吻合。

求值算法

根据以上分析，采用算法4.1即可高效地实现对RPN表达式的求值。

rpnEvaluation(expr)
输入：RPN表达式expr(假定语法正确)
输出：表达式数值
{
  引入栈S，用以存放操作数；
  while (expr尚未扫描完毕){
    从expr中读入下一元素x;
    if (x是操作数) 将x压入S;
    else { // 将x压入S
      从栈S中弹出运算符x所需数目的操作数;
      对弹出的操作数实施x运算，并将运算结果重新压入S;
    } // else
  } // while
  返回栈顶; // 也是栈底
}

除了一个辅助栈 S 外，该算法不需要借助任何更多的数据结构。此外，算法的控制流程也十分简明，只需对RPN表达式做单向的顺序扫描，既无需更多判断，也不含任何分支或回溯。

只有操作数可能需要借助栈 S 做缓存，运算符则均可直接执行而不必保留。另外，只要RPN表达式合法，在整个求值计算的过程中，当前运算符所需的操作数无论多少，都必然恰好按次序存放在当前栈的顶部。

手工转换

假设：事先未就运算符之间的优先级关系做过任何约定。

增添足够多的括号显式地指定该表达式的运算次序；
将各运算符后移，使之紧邻于其对应的右括号的右侧；
抹去所有括号；

操作数之间的相对次序在转换前后是一定保持不变的；而运算符在RPN中所处的位置有可能颠倒，但恰好就是其对应的操作数均已就绪且该运算可以执行的位置。

自动转换

代码4.7中的evaluate()算法在对表达式求值的同时，也顺便完成了从常规表达式到RPN表达式的转换。在求值过程中，该算法借助append()函数（习题【4-8】）将各操作数和运算符适时地追加至串rpn的末尾，直至得到完整的RPN表达式（习题【4-9】）。

采用的规则十分简明：凡遇到操作数，即追加至rpn；而运算符只有从栈中弹出并执行时，才被追加（与中缀表达式求值对比记忆）。这一过程与上述手工转换的方法完全等效，其正确性也因此得以确立。

将RPN自动转换过程与RPN求值过程做一对照可以发现后者只是前者的再现。

4.4 试探回溯法

4.4.1 试探与回溯

旅行商问题

在计算机中很多应用问题的解，在形式上都可以看作若干元素按特定次序构成的一个序列。以经典的旅行商问题（traveling salesman problem，TSP）为例，其目标是计算出由给定的 n 个城市构成的一个序列，使得按此序列对这些城市的环游成本（比如机票价格）最低。尽管此类问题本身的描述并不复杂，但由于所涉及元素（比如城市）的每一排列都是一个候选解，它们往往构成一个极大的搜索空间。通常其搜索空间的规模与全排列总数大体相当，为$n! = O(n^n)$。因此若采用蛮力策略，逐一生成可能的候选解并检查其是否合理，则必然无法将运行时间控制在多项式的范围以内。

剪枝

为此，必须基于对应用问题的深刻理解，利用问题本身具有的某些规律尽可能多、尽可能早地排除搜索空间中的候选解。其中一种重要的技巧就是，根据候选解的某些局部特征，以候选解子集为单位批量地排除。搜索空间多呈树状结构，而被排除的候选解往往隶属于同一分支，故这一技巧也可以形象地称作剪枝（prunning）。

与之对应的算法多呈现如下模式。从零开始，尝试逐步增加候选解的长度。更准确地，这一过程是在成批地考察具有特定前缀的所有候选解。这种从长度上逐步向目标靠近的尝试，称作试探（probing）。作为解的局部特征，特征前缀在试探的过程中一旦被发现与目标解不合，则收缩到此前一步的长度，然后继续试探下一可能的结果。特征前缀长度缩减的这类操作，称作回溯（backtracking），其效果等同于剪枝。如此，只要目标解的确存在就迟早会被发现，而且只要剪枝所依据的特征设计得当，计算的效率就会大大提高。

4.4.2 八皇后

n 皇后问题：在$n \times n$的棋盘上放置 n 个皇后，如何使得她们彼此互不攻击——此时称她们构成一个可行的棋局。对于任何整数$n \geq 4$，这就是n皇后问题。

皇后

皇后是组成棋局和最终解的基本单元，用如下代码实现对应的Queen类：

// queen.h
// 代码4.8 皇后类

struct Queen{ // 皇后类
    int x, y; // 皇后在棋盘上的位置坐标
    Queen(int xx = 0, int yy = 0) : x(xx), y(yy) {};
    bool operator == (Queen const& q) const { // 重载判等操作符，以检测不同皇后之间可能的冲突
        return (x == q.x) // 行冲突 （这一情况其实并不会发生，可省略）
        || (y == q.y) // 列冲突
        || (x + y == q.x + q.y) // 沿正对角线冲突
        || (x - y == q.x - q.y); // 沿反对角线冲突
    }
    bool operator != (Queen const& q) const { return !(*this == q); } // 重载不等操作符
};

每个皇后对象均由其在棋盘上的位置坐标确定。此外，还通过重载判等操作符，实现了对皇后位置是否相互冲突的判断。这里将同行、同列或同对角线的任意两个皇后视作“相等”，于是两个皇后冲突当且仅当二者被判作“相等”。

算法实现

基于试探回溯策略，可如代码4.9所示，实现通用的N皇后算法。

\\ placeQueens.cpp
\\ 代码4.9 N皇后算法

void placeQueens(int N){ // N皇后算法（迭代版）：采用试探/回溯的策略，借助栈记录查找的结果
    Stack<Queen> solu; // 存放（部分）解的栈
    Queen q(0, 0); // 从原点位置出发
    do {  // 反复试探、回溯
        if ( N <= solu.size() || N <= q.y){ // 若已出界，则
            q = solu.pop(); q.y++; // 回溯一行，并继续试探下一列
        } else { // 否则，试探下一行
            while ((q.y < N) && (0 <= solu.find(q))) // 通过与已有皇后的比对
            {q.y++; nCheck++;} // 尝试找到可摆放下一皇后的列
            if ( N > q.y ){ // 若存在可摆放的列，则
                solu.push(q); // 摆上当前皇后，并
                if ( N <= solu.size() ) nSolu++; // 若部分解已成为全局解，则通过全局变量nSolu计数
                q.x++; q.y = 0; // 转入下一行，从第0列开始，试探下一皇后
            }
        }
    } while ((0 < q.x) || (q.y < N)); // 所有分支均已或穷举或剪枝之后，算法结束
}

算法描述：首先将各皇后分配至每一行。然后，从空棋盘开始，逐个尝试着将他们放置到无冲突的某列。每放置好一个皇后，才继续试探下一个。若当前皇后在任何列都会造成冲突，则后续皇后的试探都必将是徒劳的，故此时应该回溯到上一皇后。

这里借助栈solu来动态地记录各皇后的列号。当该栈的规模增至 N 时，即得到全局解。该栈即可依次给出各皇后在可行棋局中所处的位置。书中101页给出了利用N皇后算法，得到四皇后问题第一个解的完整过程。

N皇后问题解的个数可能不唯一。

4.4.3 迷宫寻径

问题描述

简化版本：空间区域限定为由$n \times n$个方格组成的迷宫，除了四周的围墙，还有分布其间的若干障碍物；只能水平或垂直移动。任务是，在任意指定的起始格点与目标格点之间找出一条通路（如果的确存在）。

迷宫格点

格点是迷宫的基本组成单位，故首先需要实现的Cell类如代码4.10所示：

// Cell.h
// 代码4.10 迷宫格点类

typedef enum { AVAILABLE, ROUTE, BACKTRACKED, WALL} Status; // 迷宫单元状态
// 原始可用的、在当前路径上的、所有方向均尝试失败后回溯过的、不可用的（墙）

typedef enum { UNKNOWN, EAST, SOUTH, WEST, NORTH, NO_WAY} ESWN; // 单元的相对邻接方向
// 未定、东、南、西、北、无路可通

inline ESWN nextESWN(ESWN eswn){ return ESWN(eswn + 1); } // 依次转至下一邻接方向

struct Cell { // 迷宫格点
    int x, y; Status status; // x坐标、y坐标、类型
    ESWN incoming, outgoing; // 进入、走出方向
};

#define LABY_MAX 24 // 最大迷宫尺寸
Cell laby[LABY_MAX][LABY_MAX]; // 迷宫

可见，除了记录其位置坐标外，格点还需记录其所处的状态。共有四种可能的状态：原始可用的（AVAILABLE）、在当前路径上的（ROUTE）、所有方向均尝试失败后回溯过的（BACKTRACKED）、不可穿越的（WALL）。属于当前路径的格点，还需记录其前驱和后继格点的方向。用EAST、SOUTH、WEST、NORTH区分上、下、左、右四个连通方向。特别地，因尚未搜索到而仍处于初始AVAILABLE状态的格点，邻格的方向都是未知的（UNKNOWN）；经过回溯后处于BACKTRACKED状态的格点，与邻格之间的连通关系均已关闭，故标记为NO_WAY。

邻格查询

在路径试探过程中需反复确定当前位置的相邻格点，可如代码4.11所示实现查询功能：

// neighbor.h
// 代码4.11 查询相邻格点

inline Cell* neighbor(Cell* cell){ // 查询当前位置的相邻格点
    switch (cell -> outgoing){
        case EAST:
            return cell + LABY_MAX; // 向东
        case SOUTH:
            return cell + 1; // 向南
        case WEST:
            return cell - LABY_MAX; // 向西
        case NORTH:
            return cell - 1; // 向北
        default:
            exit(-1);
    }
}

邻格转入

在确认某一相邻格点可用之后，算法将朝对应的方向向前试探一步，同时路径延长一个单元。为此，需如代码4.12所示实现相应的格点转入功能。

// advance.h
// 代码4.12 转入相邻格点

inline Cell* advance(Cell* cell){ // 从当前位置转入相邻格点
    Cell* next;
    switch (cell -> outgoing){
        case EAST: next = cell + LABY_MAX; next -> incoming = WEST;
            break; // 向东
        case SOUTH: next = cell + 1; next -> incoming = NORTH;
            break; // 向南
        case WEST: next = cell - LABY_MAX; next -> incoming = EAST;
            break; // 向西
        case NORTH: next = cell - 1; next -> incoming = SOUTH;
            break; // 向北
        default: exit(-1);
    }
    return next;
}

算法实现

在以上功能的基础上，可基于试探回溯策略实现寻径算法如代码4.13所示：

// Laby.h
// 代码4.13

bool labyrinth(Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t){
    if ((AVAILABLE != s -> status) || (AVAILABLE != t -> status)) return false; // 退化情况
    Stack<Cell*> path; // 用栈记录通路
    s -> incoming = UNKNOWN; s -> status = ROUTE; path.push(s); // 起点
    do { // 从起点出发不断试探、回溯，直到抵达终点，或者穷尽所有可能
        Cell* c = path.top(); // 检查当前位置(栈顶)
        if (c == t) return true; // 若已抵达终点，则找到了一条通路；否则，沿尚未试探的方向继续试探
        while (NO_WAY > (c -> outgoing = nextESWN(c -> outgoing))) // 逐一检查所有方向
            if (AVAILABLE == neighbor(c) -> status) break; // 试图找到尚未试探的方向
            if (NO_WAY <= c -> outgoing) // 若所有方向都已尝试过
            {c -> status = BACKTRACKED; c = path.pop(); } // 则向后回溯一步
            else // 否则，向前试探一步
            {path.push(c = advance(c)); c -> outgoing = UNKNOWN; c -> status = ROUTE; }
    } while (!path.empty());
    return false;
}

该问题的搜索过程中，局部解是一条源自起始格点的路径，它随着试探、回溯相应地伸长、缩短。因此，这里借助栈path按次序记录组成当前路径的所有格点，并动态地随着试探、回溯做入栈、出栈操作。路径的起始格点、当前的末端格点分别对应于path的栈底和栈顶，当后者抵达目标格点时搜索成功，此时path所对应的路径即可作为全局解返回。书中P104页给出了以上迷宫寻径算法的一次运行实例。

正确性

该算法会尝试当前格点的所有相邻格点，因此通过数学归纳可知，若在找到全局解后依然继续查找，则该算法可以抵达与起始格点连通的所有格点。因此，只要目标格点与起始格点的确相互连通，则这一算法必将找出一条联接于二者之间的通路。

复杂度

算法的每一步迭代仅需常数时间，故总体时间复杂度线性正比于试探、回溯操作的总数。由于每个格点至多参与试探和回溯各一次，故亦可度量为所有被访问过的格点总数。

4.5 队列

4.5.1 概述

入队与出队

与栈一样，队列（queue）也是存放数据对象的一种容器，其中的数据对象也按线性的逻辑次序排列。队列结构同样支持对象的插入和删除，但两种操作的范围分别被限制于队列的两端——若约定新对象只能从某一端插入其中，则只能从另一端删除已有的元素。允许去除元素的一端称作队头（front），而允许插入元素的另一端称作队尾（rear）。

元素的插入与删除也是修改队列结构的两种主要形式，站在被操作对象的角度，分别称作入队（enqueue）和出队（dequeue）。

先进先出

与栈结构相反，队列中各对象的操作次序遵循所谓的先进先出（first-in-first-out，FIFO）的规律：更早（晚）出队的元素的应为更早（晚）入队者，反之，更早（晚）入队者应更早（晚）出队。

4.5.2 ADT接口

作为一种抽象数据类型，队列结构必须支持以下操作接口：

操作接口	功能
`size()`	报告队列的规模（元素总数）
`empty()`	判断队列是否为空
`enqueue(e)`	将e插至队尾
`dequeue`	删除队首对象
`front()`	引用队首对象

4.5.3 Queue模板类

由于队列可视作序列的特例，因此可将队列作为列表的派生类。利用C++的继承机制，基于之前定义的列表模板类实现队列结构并将接口重新命名。

// Queue.h
// 代码4.14 Queue模板类

#include "../List/list.h" // 以List为基类
template <typename T> class Queue: public List<T> { // 队列模板类（继承List原有接口）
public: // size()、empty()以及其它开放接口均可直接沿用
    void enqueue(T const& e){ insertAsLast(e); } // 入队：尾部插入
    T dequeue(){ return remove(first()); } // 出队：首部删除
    T& front(){ return first()->data; } // 队首
};

队列的enqueue()操作等效于将新元素作为列表的末元素插入，dequeue()操作等效于删除列表的首元素，front()操作可直接返回对列表首元素的引用。而size()及empty()等接口，均直接沿用基类的同名接口。

由于插入和删除操作分别限制于列表的末端和首端，故队列结构以上接口的时间复杂度均为常数。

套用以上思路，也可直接基于Vector模板类派生出Stack类（习题【4-2】）。

4.6 队列应用

4.6.1 循环分配器

队列结构非常适合定义和实现一套公平且高效的分配规则，这种分配规则适用于在客户(client)群体中共享某一资源(比如多个应用程序共享同一CPU)。

具体地，可以借助队列Q实现一个资源循环分配器，其总体流程大致如算法4.2所示：

RoundRobin { // 循环分配器
    Queue Q(clients); // 参与资源分配的所有客户组成队列Q
    while (!ServiceClosed()) { // 在服务关闭之前，反复地
        e = Q.dequeue(); // 队首的客户出队，并
        serve(e); // 接收服务，然后
        Q.enqueue(e); // 重新入队
    }
}

在以上所谓轮值(round robin)算法中，首先令所有参与资源分配的客户组成一个队列Q。接下来是一个反复轮回式的调度过程：取出当前位于队头的客户，将资源交予该客户使用；在经过固定的时间之后，回收资源，并令该客户重新入队。得益于队列“先进先出”的特性，如此既可在所有客户之间达成一种均衡的公平，也可使得资源得以充分利用。

这里，每位客户持续占用资源的时间，对该算法的成败至关重要。一方面，为保证响应速度，这一时间值通常都不能过大。另一方面，因占有权的切换也需要消耗一定的时间，故若该时间值取得过小，切换过于频繁，又会造成整体效率的下降。因此，往往需要通过实测确定最佳值。反过来，在单一客户使用多个资源的场合，队列也可用以保证资源的均衡使用，提高整体使用效率。

4.6.2小节以银行为例，介绍如何利用队列结构实现顾客服务的调度与优化，有兴趣的可以翻阅书中该部分内容。